class Solution {
public:
    double pow(double x, int n) {
        if (n==0) return 1;
        double ret=pow(x, n/2);
        ret=ret*ret;
        if (n%2==1) ret*=x;
        if (n%2==-1) ret*=1/x;
        return ret;
    }
};
